package A一周刷爆LeetCode.A基础班.F二叉树;

import java.util.*;

/**
 * @author wei.zhao
 * @description: 最低公共祖先节点
 * @date 2022年02月25日 17:54
 */
public class Code10_LowestCommonAncestor {

    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.left.left = new Node(4);
        head.left.right = new Node(5);
        head.right.left = new Node(6);
        head.right.right = new Node(7);
        head.left.left.left = new Node(8);
        Node node01 = head.left.left.left;
        Node node02 = head.left.right;
        System.out.println("最低公共祖先节点：" + lowestAncestor01(head, node01, node02).value);
        System.out.println("最低公共祖先节点：" + lowestAncestor02(head, node01, node02).value);
        System.out.println("最低公共祖先节点：" + lowestAncestor03(head, node01, node02).value);
    }

    // 简单粗暴
    private static Node lowestAncestor01(Node head, Node node01, Node node02) {
        if (head == null) {
            return null;
        }
        // 记录所有节点与父节点映射关系
        HashMap<Node, Node> map = new HashMap<>();
        map.put(head, null);
        LinkedList<Node> list = new LinkedList<>();
        list.add(head);
        while (!list.isEmpty()) {
            Node node = list.pop();
            if (node.left != null) {
                list.add(node.left);
                map.put(node.left, node);
            }
            if (node.right != null) {
                list.add(node.right);
                map.put(node.right, node);
            }
        }
        // 找出node01的所有祖先节点
        List<Node> node01Ancestor = new ArrayList<>();
        while (null != node01) {
            node01Ancestor.add(node01);
            node01 = map.get(node01);
        }
        // 找出node02的所有祖先节点
        Set<Node> node02Ancestor = new HashSet<>();
        while (null != node02) {
            node02Ancestor.add(node02);
            node02 = map.get(node02);
        }
        // 找出第一个公共祖先节点
        for (Node node : node01Ancestor) {
            if (node02Ancestor.contains(node)) {
                return node;
            }
        }
        return null;
    }

    // 二叉树的递归套路
    private static Node lowestAncestor02(Node head, Node node01, Node node02) {
        Info info = process(head, node01, node02);
        return info.result;
    }

    private static Info process(Node head, Node node01, Node node02) {
        if (head == null) {
            return new Info(new HashSet<>(), null);
        }
        Info left = process(head.left, node01, node02);
        Info right = process(head.right, node01, node02);
        left.set.addAll(right.set);
        left.set.add(head);
        Node result = null;
        if (left.result != null || right.result != null) {
            result = left.result != null ? left.result : right.result;
        } else if (left.set.contains(node01) && left.set.contains(node02)) {
            result = head;
        }
        return new Info(left.set, result);
    }

    public static class Info {
        public HashSet<Node> set;
        public Node result;

        public Info(HashSet<Node> set, Node result) {
            this.set = set;
            this.result = result;
        }
    }

    //巧妙解法
    private static Node lowestAncestor03(Node head, Node node01, Node node02) {
        if (head == null || head == node01 || head == node02) {
            return head;
        }
        Node left = lowestAncestor03(head.left, node01, node02);
        Node right = lowestAncestor03(head.right, node01, node02);
        if (left != null && right != null) {
            return head;
        }
        return left != null ? left : right;
    }

}